#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <math.h>

typedef struct binaryTree
{
	int val;
	struct binaryTree* left;
	struct binaryTree* right;

}bt;
int btsize(bt* pb)
{
	if (pb == NULL)
	{
		return 0;
	}
	int ret = 1;
	ret += btsize(pb->left) + btsize(pb->right);
	return ret;
}
bt* crenode(int x)
{
	bt* pb = (bt*)malloc(sizeof(bt));
	pb->val = x;
	pb->left = NULL;
	pb->right = NULL;
	return pb;
}
int treeleafsize(bt* pb)
{
	if (pb == NULL)
	{
		return 0;
	}
	if (pb->left == NULL && pb->right == NULL)
	{
		return 1;
	}
	return treeleafsize(pb->left) + treeleafsize(pb->right);
}
void preorder(bt* pb)
{
	if (pb == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", pb->val);
	preorder(pb->left);
	preorder(pb->right);
}
void inorder(bt* pb)
{
	if (pb == NULL)
	{
		printf("NULL ");
		return;
	}
	inorder(pb->left);
	printf("%d ", pb->val);
	inorder(pb->right);
}
void postorder(bt* pb)
{
	if (pb == NULL)
	{
		printf("NULL ");
		return;
	}
	postorder(pb->left);
	postorder(pb->right);
	printf("%d ", pb->val);
}
bt* createpreorder(char* str, int* pi)
{
	if (str[*(pi)++] == '#')
	{
		return NULL;
	}
	else
	{
		bt* newnode = (bt*)malloc(sizeof(bt));
		newnode->val = str[*(pi)++];
		newnode->left=createpreorder(str, pi);
		newnode->right=createpreorder(str, pi);
		return newnode;
	}
}
int deplenth(bt* pb,int* pi)
{
	if (pb == NULL)
	{
		return 0;
	}
	else
	{
		int left = 0;
		deplenth(pb->left, &left);
		int right = 0;
		deplenth(pb->right, &right);
		return left > right ? left + 1 : right + 1;
	}
}
bool isbalancetree(bt* pb,int* pi)
{
	if (pb == NULL)
	{
		*(pi) = 0;
		return true;
	}
	else
	{
		int left = 0;
		if (isbalancetree(pb->left, &left) == false)
		{
			return false;
		}
		int right = 0;
		if (isbalancetree(pb->right,&right)==false)
		{
			return false;
		}
		if (abs(left - right) > 1)
		{
			return false;
		}
		*pi = left > right ? left + 1 : right + 1;
		return true;
	}
}
void test_1()
{
	bt* bt1 = crenode(1);
	bt* bt2 = crenode(2);
	bt* bt3 = crenode(3);
	bt* bt4 = crenode(4);
	bt* bt5 = crenode(5);
	bt1->left = bt2;
	bt1->right = bt3;
	bt2->left = bt4;
	bt2->right = bt5;
	printf("%d\n", btsize(bt1));
	printf("%d\n", treeleafsize(bt1));
	preorder(bt1);
	printf("\n");
	inorder(bt1);
	printf("\n");
	postorder(bt1);
}

void main_7()
{
	test_1();
}